package mine.code.question.单调栈;

import org.junit.Test;

import java.util.Stack;

/**
 * 给定一个仅包含小写字母的字符串，去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 * * <p>
 * * 示例 1:
 * * 输入: "bcabc"
 * * 输出: "abc"
 * * <p>
 * * 示例 2:
 * * 输入: "cbacdcbc"
 * * 输出: "acdb"
 *
 * @author caijinnan
 * @date 2019/12/19 17:08
 */
public class 去除重复字母 {

    @Test
    public void run() {
        String str = "cbacdcbc";
        //"acdb"
        System.out.println(removeDuplicateLetters(str));
    }

    public String removeDuplicateLetters(String s) {
        int[] characterNum = new int[26];
        boolean[] inStack = new boolean[26];
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            characterNum[c % 97] += 1;
        }
        for (char charTemp : chars) {
            characterNum[charTemp % 97] -= 1;
            if (inStack[charTemp % 97]) {
                continue;
            }
            while (!stack.empty() && charTemp < stack.peek()) {
                if (characterNum[stack.peek() % 97] == 0) {
                    break;
                }
                inStack[stack.peek() % 97] = false;
                stack.pop();
            }
            stack.push(charTemp);
            inStack[charTemp % 97] = true;
        }
        StringBuilder str = new StringBuilder();
        for (Character character : stack) {
            str.append(character);
        }
        return str.toString();
    }

}
